package chapter03;

public class MinDepth111 {
    /**
     * 树形dp
     * 根节点到叶子节点间最少的节点数 假设左右子树可以给出子树到叶子节点的最少节点数 最少节点数加1就是根节点的最少节点数
     * 递归出口
     * 1).x==null
     *      return 0
     * 2).x.left==null&&x.right==null
     *      return 1
     * 3).dep=Integer.MAX_VALUE
     *    if x.left!=null dep=min(dep,process(x.left))
     *    if x.right!=null dep=min(dep,process(x.right))
     *    return dep+1
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return process(root);
    }


    public int process(TreeNode x){
        if(x==null){
            return 0;
        }
        if(x.left==null&&x.right==null){
            return 1;
        }
        int dep=Integer.MAX_VALUE;
        if(x.left!=null){
            dep=Math.min(process(x.left),dep);
        }
        if(x.right!=null){
            dep=Math.min(process(x.right),dep);
        }
       return dep+1;
    }
}

